package myalg.binsearch;

/**
 * @author Pavel Belevich
 *         Date: Jun 25, 2012
 *         Time: 3:20:52 PM
 */
public class Main {

    public static int binarySearch(int[] a, int k) {
        int i = 0;
        int j = a.length - 1;
        int m;
        if (a.length > 0 && a[i] <= k && k <= a[j]) {
            while (i <= j) {
                m = i + (j-i)/2;
                if (k > a[m]) {
                    i = m + 1;
                } else if (k < a[m]) {
                    j = m - 1;
                } else {
                    return m;
                }
            }
        }
        return -1;
    }

    public static int binarySearch2(int[] a, int k) {
        int i = 0;
        int j = a.length - 1;
        return binarySearch2(a, k, i, j);
    }

    public static int binarySearch2(int[] a, int k, int i, int j) {
        int m;
        if (a.length > 0 && a[i] <= k && k <= a[j] && i <= j) {
            m = i + (j-i)/2;
            if (k > a[m]) {
                i = m + 1;
                return binarySearch2(a, k, i, j);
            } else if (k < a[m]) {
                j = m - 1;
                return binarySearch2(a, k, i, j);
            } else {
                return m;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] a = {1,3,4,6,8,10,13,17,20};
        for (int i = 0 ; i < 50 ; i++) {
            System.out.println(i-25 + "\t" + binarySearch2(a, i-25));
        }
    }
    
}
